package priv.conceit.study.leetcode.simple.official;

import java.util.HashMap;
import java.util.Objects;
import java.util.Stack;

/**
 * 编号0020
 * 有效的括号
 * <a href="https://leetcode-cn.com/problems/valid-parentheses/"></a>
 * 判断一个整数是否是回文数。回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。
 * 给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效
 * 有效字符串需满足：
 * 左括号必须用相同类型的右括号闭合。
 * 左括号必须以正确的顺序闭合。
 *
 * 示例 1:
 * 输入: "()"
 * 输出: true
 *
 * 示例 2:
 * 输入: "()[]{}"
 * 输出: true
 *
 * 示例 3:
 * 输入: "(]"
 * 输出: false
 *
 * 示例 4:
 * 输入: "([)]"
 * 输出: false
 *
 * 示例 5:
 * 输入: "{[]}"
 * 输出: true
 *
 * 用栈来实现
 * 获取input的String char数组
 * 从左边开始入栈
 * 如果是左边的括号
 * 则右边必须有对应相同类型的右括号
 * 找到则双方一起出栈
 * 否则继续向后寻找，至栈顶还没有找到则返回false
 *
 * 正常情况下 到栈顶应该为空
 *
 *
 *@author conceit
 */
 public class ValidParentheses {

 	public static void main(String[] args) {
		boolean flag=new ValidParentheses().isValid("(])");
		System.out.println(flag);
	}

	final static HashMap<Character,Character> hashMap=new HashMap<>();
	static{
		hashMap.put('(',')');
		hashMap.put('[',']');
		hashMap.put('{','}');
	}

	public boolean isValid(String s) {
		if(Objects.isNull(s)){
			return Boolean.FALSE;
		}
		Stack<Character> stack=new Stack();
		for (int i=0;i<s.length();i++){
			char cur=s.charAt(i);
			if(!hashMap.containsKey(cur)&&!hashMap.containsValue(cur)){
				return Boolean.FALSE;
			}
			//left or right
			if(hashMap.containsKey(cur)){
				stack.push(cur);
			}
			/**
			 * 如果是right的话 需要进行
			 * 0-校验 栈是否为空 为空直接打回
			 * 1-看是否栈顶 和right是否为一对
			 * 2-是的话栈顶 出栈
			 * 3-不是则返回false
			 */
			else{
				if(stack.empty()){
					return Boolean.FALSE;
				}
				char element=stack.peek();
				//如果栈顶左括号==map.get(栈顶左括号)
				//栈顶出栈
				if(hashMap.get(element)==cur){
					stack.pop();
				}else{
					return Boolean.FALSE;
				}
			}
		}

		if(stack.empty()){
			return Boolean.TRUE;
		}

 		return Boolean.FALSE;
	}


 }
